package 剑指offer;

public class _36二叉搜索树与双向链表 {
    class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val,Node _left,Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    };

    Node head, pre;
    public Node treeToDoublyList1(Node root) {
        if(root == null) return null;

        dfs(root);

        pre.right = head;
        head.left = pre;// 头尾连接

        return head;
    }

    public void dfs(Node cur) {
        if(cur == null) return;
        dfs(cur.left);
        if(pre == null) {
            head = cur;  //找到了头
        } else {
            pre.right = cur; // 连接左子树
        }

        cur.left = pre; // 根和左边连上（双向）

        pre = cur; // pre继续往左走 或者 往右走（看走的是cur.left 还是 cur.right）

        dfs(cur.right);
    }


    public Node treeToDoublyList(Node root) {
        if(root == null || (root.left == null && root.right == null)){
            return root;
        }
        Node left = treeToDoublyList(root.left);
        Node leftTail = left;
        while(leftTail != null && leftTail.right != null){
            leftTail = leftTail.right;
        }
        if(root.left != null){
            leftTail.right = root;
            root.left = leftTail;
        }
        Node right = treeToDoublyList(root.right);
        if(root.right != null){
            right.left = root;
            root.right = right;
        }
        return root.left == null ? root : left;
    }
}
